package com.github.yangyishe.p300;

/**
 * 211. 添加与搜索单词 - 数据结构设计
 * https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 *
 * 实现词典类 WordDictionary ：
 *
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
 *
 *
 * 示例：
 *
 * 输入：
 * ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
 * [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
 * 输出：
 * [null,null,null,null,false,true,true,true]
 *
 * 解释：
 * WordDictionary wordDictionary = new WordDictionary();
 * wordDictionary.addWord("bad");
 * wordDictionary.addWord("dad");
 * wordDictionary.addWord("mad");
 * wordDictionary.search("pad"); // 返回 False
 * wordDictionary.search("bad"); // 返回 True
 * wordDictionary.search(".ad"); // 返回 True
 * wordDictionary.search("b.."); // 返回 True
 *
 *
 * 提示：
 *
 * 1 <= word.length <= 25
 * addWord 中的 word 由小写英文字母组成
 * search 中的 word 由 '.' 或小写英文字母组成
 * 最多调用 104 次 addWord 和 search
 */
public class Problem211 {
    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        System.out.println(wordDictionary.search("pad")); // 返回 False
        System.out.println(wordDictionary.search("bad")); // 返回 True
        System.out.println(wordDictionary.search(".ad")); // 返回 True
        System.out.println(wordDictionary.search("b..")); // 返回 True
    }
}

/**
 * 思路:
 * 与p208较为相似
 * 区别在于, 还需要支持单字符模糊匹配.
 *
 * 如果出现了统配符,则需要对children下所有的字符均进行查找, 只要有一个符合要求就返回true
 *
 */
class WordDictionary {
    private WordDictionaryNode root;

    public WordDictionary() {
        root=new WordDictionaryNode();
    }

    public void addWord(String word) {
        root.addWord(word.toCharArray(),0);
    }

    public boolean search(String word) {
        return root.search(word.toCharArray(),0);
    }
}

class WordDictionaryNode{
    boolean isEnd;
    WordDictionaryNode[] children;

    public WordDictionaryNode() {
        children=new WordDictionaryNode[26];
    }

    public void addWord(char[] chars,int index){
        int childIndex=chars[index]-'a';
        if(children[childIndex]==null){
            children[childIndex]=new WordDictionaryNode();
        }
        if(index<chars.length-1){
            children[childIndex].addWord(chars, index+1);
        }else{
            children[childIndex].isEnd=true;
        }
    }

    public boolean search(char[] chars,int index){
        if(chars[index]=='.'){
            boolean flag=false;
            for (WordDictionaryNode child : children) {
                if(child!=null){
                    if(index==chars.length-1){
                        flag=child.isEnd;
                    }else{
                        flag=child.search(chars,index+1);
                    }
                    if(flag){
                        break;
                    }
                }
            }
            return flag;
        }
        int childIndex=chars[index]-'a';
        if(children[childIndex]==null){
            return false;
        }
        if(index<chars.length-1){
            return children[childIndex].search(chars,index+1);
        }else{
            return children[childIndex].isEnd;
        }

    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */
